var AStar = {
	/**
	 * Read all about it at  http://en.wikipedia.org/wiki/A*_search_algorithm
	 *
	 * This is a *really* straight port... counting on js wildness to 
	 * do the right thing... but it'll need some help. 
	 * 
	 * Need to pass in:
	 *
	 * heuristic_estimate_of_distance 
	 * neighbor_nodes( a )              : return the 
	 * dist_between( a, b )             : a and b will be neighboring nodes                   
	 * equals(a,b)                      : return true if a and b are equal
	 *
	 * see bottom of file for some lame implementations
	 *
	 * Note: this version now uses a sorted list for the f values and uses
	 *       Util.insertIntoOrdered do binary insert (log(n), baby!)
	 *
	 */
	astar: function( 
		  start
		, goal
		, heuristic_estimate_of_distance
		, neighbor_nodes 
		, dist_between
		, equals
	) {

		var closedset = []; /* The set of nodes already evaluated     */
		var openset   = []; /* The set of nodes to be evaluated       */
		var g_score   = []; /* distance from start along optimal path */
		var h_score   = []; /* distance estimate to the goal          */
		var f_score   = []; /* sum of g + h                           */
		var came_from = []; /* the node that let to given node        */
		var path      = []; /* the path from the start to the goal    */
		var f_scorez  = []; /* sorted list of openset nodes by f      */

		openset[ start ] = true;
		g_score[ start ] = 0;
		h_score[ start ] = heuristic_estimate_of_distance( start, goal );
		f_score[ start ] = g_score[ start ] + h_score[ start ]; 
		f_scorez.push( start );
	
		var max_iterations = 2096; /* i am chicken... */
		var iterations = 0;

		while ( 0 != f_scorez.length ) {
			//Util.log( '---------------------------------------------------' );
			//Util.log( 'openset: ' + Util.keys( openset ) );
			//Util.log( 'closedset: ' + Util.keys( closedset ) );

			if ( iterations++ > max_iterations ) {
				Util.log( 'got scaret!' );
				break;
			}

			// x = the node in openset having the lowest f_score[] value
			var x = f_scorez.shift();
			//Util.log( 'Current champ: ' + x + ' f=' + f_score[ x ] );

			if ( equals( x, goal ) ) {
				//Util.log( 'suck-sess: ' + x + ' is ' + goal );
				path = AStar.reconstruct_path( came_from, goal )
				break;
			}
			
			openset[ x ]   = false;
			closedset[ x ] = x;

			var neighbors = neighbor_nodes( x );
			//Util.log( x + ' neighbors are {' + neighbors + '}' );
			for ( var i in neighbors ) {
				var y = neighbors[ i ];
				if ( closedset[ y ] ) {
					//Util.log( 'skip ' + y );
					continue;
				}

				var tentative_g_score   = g_score[ x ] + dist_between( x, y );
				var tentative_is_better = false;

				if ( !openset[ y ] ) {
					//Util.log( 'add ' + y + ' = ' + y.i + ',' + y.j );
					openset[ y ] = true;
					h_score[ y ] = heuristic_estimate_of_distance(y, goal)
					tentative_is_better = true;
				} else 
				if ( tentative_g_score < g_score[y] ) {
					tentative_is_better = true;
				} 

				if ( true == tentative_is_better ) {
					came_from[ y ] = x;
					g_score[ y ]   = tentative_g_score;
					f_score[ y ]   = g_score[ y ] + h_score[ y ];
					Util.insertIntoOrdered( 
						f_scorez
						, y
						, function( a, b ) { return f_score[ a ] > f_score[ b ]; }
					);
				}
			}

		}
		return path ? path : [];
	}

	, reconstruct_path: function( came_from, current_node ) {
		var path = (
			came_from[ current_node ] 
			? AStar.reconstruct_path( came_from, came_from[ current_node ] )
			: []
		);
		path.push( current_node );
		return path;
	}

	/* 
		these are novelty implementations: they are based off an imaginary
		grid-based (i,j) node structure
	*/

	 , heuristic_estimate_of_distance : function( a, b ) {
		return ( a.i - b.i ) * ( a.i - b.i ) + ( a.j - b.j ) * ( a.j - b.j );
	 }
	 , neighbor_nodes : function( a ) {
		return []; // so alone... 
	 }
	 , dist_between : function( a, b ){
		 return ( a.i == b.i || a.j == b.j ) ? 1 : 2;
	 }
	 , equals : function( a, b ) {
		 return a.i == b.i && a.j == b.j;
	 }

};

